This invention elates to a methos for secure distribution of data and/or programs.
Methods for distribution of software SW by an issuing unit to a large number of like terminals or smart cards are being increasingly used in particular through the possibilities of telecommunication. The issuing unit generates an electronic signature of software SW using a public-key method in order to ensure the authenticity of software SW.
The issuing unit uses a commonly known method to calculate for software SW to be signed certificate M containing, along with other data, mainly hash value H(SW) dependent on the software. H(SW) is a publicly known hashing method. The issuing unit encrypts certificate M with its private key D. The result of said encryption is electronic signature S. The issuing unit sends software SW together with signature S to the terminal or smart card. There, value M of the generated certificate is calculated from signature S using public key E=Dxe2x88x921 of the issuing unit. Further, the terminal or smart card, i.e. the receiving unit, calculates hash value H(SW) of software SW and tests whether H(SW) is correctly entered in certificate M. If this is the case, the receiving unit accepts software SW, otherwise it rejects software SW.
The best known public-key method for generating electronic signatures is the RSA method. A variant of the RSA method is the Rabin method or a variant of the Rabin method according to Williams.
The issuing unit randomly selects two primes P=3 mod 8 and Q=7 mod 8. These constitute the private key of the issuing unit. The public key is the value N=P*Q. For signing message M the issuing unit calculates the signature
S=Mxc2xd mod (P*Q).
The receiving unit can verify the signature by calculating
M=S2 mod N.
The security of the Rabin method is based on the fact that it is easy to extract the square root of a number modulo a prime (if one exists), while extracting the square root of a randomly selected number modulo a composite number is at least as difficult as factorizing that composite number.
Not every number is a quadratic residue modulo prime P or Q; furthermore, quadratic residues mod P and Q normally have four square roots. Due to the special choice of P and Q, for any number M exactly one of the four numbers M, Nxe2x88x92M, N/2 and Nxe2x88x92M/2 is a quadratic residue mod P and mod Q (when M is odd N/2 is replaced by (M+N)/2 mod P*Q). This statement follows from the additional theorems for the quadratic reciprocity law.
If one requires for message M the additional condition M=4 mod 8, the following holds because of the relation N=P*Q=3*7=5 (mod 8):
M=0, Nxe2x88x92M=1, M/2=2, Mxe2x88x92N/2=3 (mod 4)
i.e. the four numbers M, Nxe2x88x92M, M/2 and Nxe2x88x92M/2 differ in the last two bit positions.
For signing message M the issuing unit first tests which of the four values M, Nxe2x88x92M, N/2 or Nxe2x88x92N/2 is a quadratic residue mod P and mod Q. This can be done effectively by calculating the Jacobian symbols (N/P) and (M/Q):
Mxe2x80x2=M if (M/P)=1, (M/Q)=1;
Mxe2x80x2=xe2x88x92M if (M/P)=xe2x88x921, (M/Q)=xe2x88x921;
Mxe2x80x2=M/2 if (M/P)=xe2x88x921, (M/Q)=1;
Mxe2x80x2=xe2x88x92M/2 if (M/P)=1, (M/Q)=xe2x88x921;
Let Mxe2x80x2 be the value meeting both conditions. The signature for message M is then:
S=(Mxe2x80x2)(P*Qxe2x88x92Pxe2x88x92Q+5)/8 mod N
It thus holds that:
S2=Mxe2x80x2*(Mxe2x80x2)[(Pxe2x88x921)/2]*[(Qxe2x88x921,/2] mod N
Since Mxe2x80x2 is a quadratic residue mod P it follows by Fermat""s small theorem that (Mxe2x80x2)[(Pxe2x88x921)/2]=1 mod P. Analogously it holds that (Mxe2x80x2)[(Qxe2x88x921)/2]=1 mod Q. By the Chinese remainder theorem it further follows that (Mxe2x80x2)[(Pxe2x88x921)/2]*[(Qxe2x88x921)/2]=1 mod P*Q. It thus holds that
S2=Mxe2x80x2 mod N=P*Q.
For verifying signature S terminal B first calculates the value
Mxe2x80x2=S2 mod N
Since when M=4 mod 8 is given the four possible values for Mxe2x80x2 differ in the last two bit positions, M can be easily calculated from Mxe2x80x2:
M=Mxe2x80x2 if Mxe2x80x2=0 mod 4;
M=Nxe2x88x92Mxe2x80x2 if Mxe2x80x2=1 mod 4;
M=2Mxe2x80x2 if Mxe2x80x2=2 mod 4;
M=2(Nxe2x88x92Mxe2x80x2) if Mxe2x80x2=3 mod 4;
For verifying a signature on the smart card or terminal B a modular multiplication is necessary; i.e. the receiving unit calculates:
Mxe2x80x2=S*S mod N
This necessitates a multiplication and a division. The division is considerably more elaborate than the multiplication. The disadvantage of the known procedure for verifying a signature is thus that the software receiving unit, which usually has less computing capacity than the issuing unit, must perform a comparatively elaborate calculating operation.
It is known from Menezes, xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d, 1997, CRC Press, New York, XP002112400, to verify an electronic signature using the Montgomery multiplication method.
European patent specification EP-A-0 566 498 discloses a method for secure distribution of data and/or programs wherein the data to be transmitted are provided with an electronic signature which is checked by the receiver. To check the signature the receiver implements modular multiplication according to the Montgomery method.
The disadvantage of known methods is that when software is distributed to units having low computer power, the verification of the signature reaches the limits of computer power.
It is therefore the object of the invention to state a method for secure distribution of software which avoids the above disadvantages.
This problem is solved by the characterizing feature of the present invention and the advantageous embodiments thereof.
It is therefore the problem of the invention to state a method for secure distribution of software which avoids the above disadvantages.
This problem is solved by the characterizing features of claim 1 starting out from the features of the preamble of claim 1.
Advantageous embodiments of the invention are stated in the dependent claims.
According to the invention one verifies the electronic signature using a method for implementing modular multiplication according to the Montgomery method instead of the usual standard methods for long-number arithmetic (trial division). The Montgomery method describes a faster method for modular multiplication calculating instead of the product Z=X*Y modulo N the following value:
Z0=X*Y*Lxe2x88x92i mod N
L is the basis on which the long-number arithmetic is performed. Typically L=28 is used with an 8-bit processor, L=216 with a 16-bit processor, etc. The value i must be at least great enough so as to fulfill the condition
Li greater than N.
The advantage of the Montgomery method is that the trial division step in modular multiplication is omitted. On the other hand, multiplication is additionally done by the undesirable factor Lxe2x88x92i mod N. This undesirable effect can be compensated in modular exponentiation according to the RSA method as follows.
Calculation of an RSA exponentiation AE mod N is usually performed by repeated application of the laws of exponents A2x=Ax*Ax (mod N) and A2x+1=(Ax*Ax)*A (mod N). In the first step X=(E/2) is set, and in the following steps X is replaced by (X/2) until X=1 holds, (X) being here the greatest integer  less than =X. Modular exponentiation thus in fact amounts to a sequence of squarings and multiplications based on A (mod N).
In modular exponentiation by the Montgomery method the following is calculated:
A0=(A0*(L2i mod N))*Li mod N
This requires one Montgomery multiplication with the fixed value L2i mod N and it holds that A0=A*Li mod N. It obviously holds that:
Ax*Ay*Li=(Ax*Li)*(Ay*Li)*Li=Ax+y*Li mod N.
Using (Ax*Li) and (Ay*Li) the value Ax*Ay*Li can thus be calculated by a single Montgomery multiplication. Beginning with the value A0=A1*Li the value AE*Li can be easily calculated by repeated squaring and multiplying by A0. A further Montgomery multiplication of the intermediate result AE*Li by 1 provides the desired final result AE.
In modular exponentiation with an exponent selected randomly in the range 1, . . . , N a necessary compensation involves relatively low additional computing effort.
When software is downloaded to a terminal or smart card, the signature test must be performed there. Since the terminal normally has little computing power, the signature test must be realized as simply as possible.
In the conventional combination of Rabin""s signature test with Montgomery multiplication, signature S is transferred to terminal B.
Terminal B calculates:
M0=(S*S)*Lxe2x88x92i mod N
Mxe2x80x2=(M0*(L2i mod N))Lxe2x88x92i mod N
Obviously Mxe2x80x2=S2 mod N then holds. This method requires two Montgomery multiplications mod N and the value (L2i mod N) must also be stored in the receiving unit.